//
// Created by bleedingfight on 2020/7/8.
//
#include "fourSum.h"
std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target){
    int size = nums.size();
    std::vector<std::vector<int>>result;
    std::sort(nums.begin(),nums.end());
    if(size<4)
        return result;
    for(int left=0;left<size;left++){
        if(nums[left]>0)
            break;
        int right=size-1;
        while (left<right&&right>=3){
            int left_second = left+1;
            int right_second = right-1;
            int left_value = nums[left];
            int left_second_value = nums[left_second];
            int right_second_value = nums[right_second];
            int temp = nums[2];
            int right_value = nums[right];
            int sum_result = nums[left]+nums[left_second]+nums[right_second]+nums[right];
            while (left_second<right_second){
                if(sum_result==target){
                    result.push_back({nums[left],nums[left_second],nums[right_second],nums[right]});
                    while (left_second<right_second&&nums[left_second]==nums[left_second+1])
                        left_second++;
                    while (left_second<right_second&&nums[right_second]==nums[right_second-1])
                        right_second--;
                    left_second++;
                    right_second--;
                }
                else if(left_second<right_second&&sum_result>target)
                    right_second--;
                else if(left_second<right_second&&sum_result<target)
                    left_second++;
            }
            right--;
        }
    }
    return result;
}

